#!/usr/bin/python3
# -*- coding:utf-8 -*-
# __author__ == taoyulong2018@gmail.com
# __time__ == 2023/7/14 19:03
# ===========================================
#       题目名称： 79. 单词搜索
#       题目地址： https://leetcode.cn/problems/word-search/
#       题目描述： https://note.youdao.com/s/LWYgPSzT
# ===========================================
import math


class Solution:

    def exist(self, board, word):
        """
             [[(0,0),],]    判断下一个是否符合要求 上下左右
        """
        # 1. 单词个数为1
        if len(word) == 1:
            for x in range(len(board)):
                if word in board[x]:
                    return True
            return False
        # 找出board中所有改棋子的位置
        chessman_dict = {}  # k 棋子名称 v 可能的位置 [(), ()]
        for x in range(len(board)):
            for y in range(len(board[x])):
                chessman = board[x][y]
                if chessman in chessman_dict.keys():
                    chessman_dict[chessman].append((x, y))
                else:
                    chessman_dict[chessman] = [(x, y), ]
        # 2. word单词board中不含有
        for chessman in word:
            if chessman not in chessman_dict.keys():
                return False
        # 3. 其他
        is_find = False
        chessboards = []  # 棋盘
        for index, chessman in enumerate(word):  # 遍历得出棋子
            # 找出对应棋子的位置
            if chessman not in chessman_dict.keys():
                break
            steps = chessman_dict[chessman]  # 获取步数
            if index == 0:  # 起步
                for step in steps:
                    chessboards.append([step, ])
            elif index == len(word) - 1:  # 结尾
                for chessboard in chessboards:
                    last_step = chessboard[-1]  # 最后一步
                    for step in steps:
                        if step in chessboard:
                            continue
                        # 判断 step 是否和 last_step 相连
                        # 使用欧几里得距离：计算两个坐标点之间的欧几里得距离，并判断距离是否小于等于1（或者其他适当的阈值）。
                        # 如果距离小于等于1，则可以认为这两个坐标点是相连的。
                        distance = math.sqrt((last_step[0] - step[0]) ** 2 + (last_step[1] - step[1]) ** 2)
                        if distance <= 1:
                            is_find = True
                            break
                    if is_find:
                        break
            else:
                temp_chessboards = []
                for chessboard in chessboards:
                    last_step = chessboard[-1]  # 最后一步
                    for step in steps:
                        if step in chessboard:
                            continue
                        # 判断 step 是否和 last_step 相连
                        # 使用欧几里得距离：计算两个坐标点之间的欧几里得距离，并判断距离是否小于等于1（或者其他适当的阈值）。
                        # 如果距离小于等于1，则可以认为这两个坐标点是相连的。
                        distance = math.sqrt((last_step[0] - step[0]) ** 2 + (last_step[1] - step[1]) ** 2)
                        if distance <= 1:
                            temp_chessboard = chessboard.copy()
                            temp_chessboard.append(step)
                            temp_chessboards.append(temp_chessboard)
                chessboards = temp_chessboards
        return is_find

    def exist4(self, board, word):
        """
            超时
        """
        if not board or not board[0]:
            return False
        letter_map = dict()  # 定义字符map
        # 1. 找到所有合乎可能的坐标
        for x in range(len(board)):
            for y in range(len(board[x])):
                if board[x][y] not in word:
                    continue
                if board[x][y] in letter_map.keys():
                    letter_map[board[x][y]].append((x, y,))
                else:
                    letter_map[board[x][y]] = [(x, y,), ]
        print(letter_map)
        # 2. 根据坐标进行排序 判断是否连贯
        boards_list = []
        for index, letter in enumerate(word):
            temp_boards_list = []
            for step in letter_map[letter]:
                if index == 0:
                    temp_boards_list.append([step, ])
                else:
                    for boards in boards_list:
                        if step in boards:
                            continue
                        temp_boards = boards.copy()
                        temp_boards.append(step)
                        temp_boards_list.append(temp_boards)
            boards_list = temp_boards_list
        # 检查坐标是否连贯
        for boards in boards_list:
            p1, p2 = 0, 1
            is_consistent = True  # 是否连贯
            while p1 < p2 < len(boards):
                """
                        使用欧几里得距离：计算两个坐标点之间的欧几里得距离，并判断距离是否小于等于1（或者其他适当的阈值）。
                    如果距离小于等于1，则可以认为这两个坐标点是相连的。
                """
                if math.sqrt((boards[p1][0] - boards[p2][0]) ** 2 + (boards[p1][1] - boards[p2][1]) ** 2) > 1:
                    is_consistent = False
                    break
                p1 = p2
                p2 += 1
            if is_consistent:
                return is_consistent
        return False

    def exist3(self, board, word):
        if not board or not board[0]:
            return False

        m, n = len(board), len(board[0])
        visited = [[False] * n for _ in range(m)]

        def backtrack(i, j, k):
            if k == len(word):
                return True
            if i < 0 or i >= m or j < 0 or j >= n or visited[i][j] or board[i][j] != word[k]:
                return False

            visited[i][j] = True
            res = backtrack(i + 1, j, k + 1) or backtrack(i - 1, j, k + 1) or backtrack(i, j + 1, k + 1) or backtrack(i, j - 1, k + 1)
            visited[i][j] = False
            return res

        for i in range(m):
            for j in range(n):
                if backtrack(i, j, 0):
                    return True

        return False

    def exist2(self, board, word):
        """
            效率有问题
        """
        # 1. 先找到单词对应字母的下标 然后根据下标是否连贯来做出判断
        letter_dict = {}  # k 字母 v （）对应下标
        for x in range(len(board)):
            for y in range(len(board[x])):
                if board[x][y] not in word:
                    continue
                if board[x][y] in letter_dict.keys():
                    letter_dict[board[x][y]].append((x, y))
                else:
                    letter_dict[board[x][y]] = [(x, y)]
        # 2. 切割单词 找到对应的字母
        boards = set()  # 所有的可能性
        for letter in word:
            if not letter_dict.get(letter):
                boards = set()  # 清空
                break
            array = letter_dict[letter]  # 获取下一个单词所在的下标
            if not boards:
                for item in array:
                    boards.add((item,))
            else:
                temp_boards = set()
                for index, cur_board in enumerate(boards):
                    for item in array:
                        temp_board = cur_board + (item,)
                        temp_boards.add(temp_board)
                boards = temp_boards
        # 去重 判断里面是否有相同的坐标
        boards = {item for item in boards if len(set(item)) == len(word)}
        # 判断是否为空
        if not boards:
            return False
        # 3. 看看坐标是否合适 是否连贯
        for board in boards:
            x, y = board[0]
            is_coherent = True
            for index in range(1, len(board)):
                step = board[index]
                if not ((x + 1, y) == step or (x, y + 1) == step or (x - 1, y) == step or (x, y - 1) == step):
                    is_coherent = False
                    break
                x, y = step
            if is_coherent:
                return True
        return False


if __name__ == '__main__':
    s = Solution()
    # True
    print(s.exist(board=[["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word="ABCCED"))
    # True
    print(s.exist(board=[["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word="SEE"))
    # False
    print(s.exist(board=[["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]], word="ABCB"))
    # False
    print(s.exist(board=[["A", "B"], ["C", "D"]], word="ABCD"))
    # True
    print(s.exist(board=[["A", "A", "A", "A"], ["A", "A", "A", "A"], ["A", "A", "A", "A"], ["A", "A", "A", "A"]], word="AAAAAAAAAAAA"))
    # True
    print(s.exist(board=[["A"]], word="A"))
    # True
    print(s.exist(board=[["B", "B"], ["A", "B"], ["B", "A"]], word="A"))
    # False
    print(s.exist(board=[["A", "A", "A", "A", "A", "A"], ["A", "A", "A", "A", "A", "A"], ["A", "A", "A", "A", "A", "A"], ["A", "A", "A", "A", "A", "A"], ["A", "A", "A", "A", "A", "A"], ["A", "A", "A", "A", "A", "A"]], word="AAAAAAAAAAAAAAB"))
